package data_structure.graph;

/**
 * Created by l19743 on 2020/12/11.
 */
public class Graph {

    public static void main(String[] args) {
        int[][] array =new int[][]{{0, 0, 1, 1, 0, 0},
                                   {0, 0, 1, 0, 0, 0},
                                   {1, 1, 0, 0, 0, 0},
                                   {0, 0, 1, 0, 1, 0},
                                   {0, 0, 0, 1, 0, 1},
                                   {0, 0, 0, 0, 1, 0}};
        dfs(0,array);
        System.out.println("dfs end............");
        bfs(array);
    }

    /**
    * dfs 遍历
    * */
    public static void dfs(int node,int[][] a){
        int[] help = new int[a.length];//用来记录已经遍历过的元素
        help[node]=1;
        System.out.print(node);
        for (int i = 0; i < a[node].length; ++i) {
            if (help[i]==0&&i != node&&a[node][i]==1) {
                dfs(i, a);
            }
        }
    }

    /**
     *
     * bfs遍历
     * */
    public static void bfs(int[][] a){
        int[] queue=new int[a.length];
        int[] help = new int[a.length];
        int cnt=1;
        queue[0]=0;//将A作为起始顶点加入队列
        help[0]=1;
        System.out.println(0);
        for (int i=0;i<cnt;++i){
            for (int j=0;j<a[queue[i]].length;++j){
                if (queue[i]!=j&&a[queue[i]][j]==1&&help[j]==0){
                    help[queue[i]]=1;
                    queue[cnt++]=j;
                    System.out.println(j);
                }
            }
        }

    }
}
